package com.practice.algorithm;


import java.util.ArrayList;
import java.util.List;

/**
 * 素数筛法
 * @author 不鄢
 */
public class PrimeTest {
    /**
     * 使用素数筛法找出小于等于 n 的所有素数
     * @param n 目标范围
     * @return 包含所有小于等于 n 的素数的列表
     */
    public static List<Integer> sieveOfEratosthenes(int n){
        boolean[] isPrime = new boolean[n+1];
        for (int i = 2; i <= n; i++){
            isPrime[i] = true;
        }

        // 标记非素数
        // 从2开始，将其倍数标记为非素数，直到根号n为止
        for(int p = 2; p*p <= n; p++){
            if(isPrime[p]){
                for(int i = p*p; i <= n; i += p){
                    isPrime[i] = false;
                }
            }
        }

        // 收集所有素数
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 30;
        List<Integer> primes = sieveOfEratosthenes(n);
        System.out.println("小于等于 " + n + " 的素数有: " + primes);
    }
}
